// https://leetcode-cn.com/problems/valid-parenthesis-string/
/**
 * @param {string} s
 * @return {boolean}
 */
// 题解：https://leetcode-cn.com/problems/valid-parenthesis-string/solution/you-xiao-de-gua-hao-zi-fu-chuan-by-leetc-osi3/
// 贪心法
var checkValidString1 = function (s) {
    let min = max = 0,// 未匹配左括号的最小值和最大值
        len = s.length;
    for (let i = 0; i < len; i++) {
        const t = s[i];
        if (t === "(") {
            min++;
            max++;
        } else if (t === ")") {
            min = Math.max(min - 1, 0);
            max--;
            if (max < 0) {
                return false;
            }
        } else {
            min = Math.max(min - 1, 0);
            max++;
        }
    }
    return min === 0;
};
// 栈
var checkValidString2 = function (s) {
    const starStack = [], leftStack = [], len = s.length;
    for (let i = 0; i < len; i++) {
        const item = s[i];
        if (item === "(") {
            leftStack.push(i);
        } else if (item === "*") {
            starStack.push(i);
        } else {
            if (leftStack.length > 0) {
                leftStack.pop();
            } else {
                if (starStack.length) {
                    starStack.pop();
                } else {
                    return false;
                }
            }
        }
    }
    while (leftStack.length && starStack.length) {
        let left = leftStack.pop(),
            star = starStack.pop();
        if (left > star) {
            return false;
        }
    }
    return leftStack.length === 0;
};
// 动态规划
var checkValidString = function (s) {
    const n = s.length;
    // const dp = new Array(n).fill(0).map(() => new Array(n).fill(false));
    const dp = Array.from(Array(n), () => Array(n).fill(false));
    for (let i = 0; i < n; i++) {
        if (s[i] === "*") {
            dp[i][i] = true;
        }
    }
    for (let i = 1; i < n; i++) {
        const c1 = s[i - 1], c2 = s[i];
        dp[i - 1][i] = (c1 === "(" || c1 === "*") && (c2 === ")" || c2 === "*");
    }
    for (let i = n - 3; i >= 0; i--) {
        const c1 = s[i];
        for (let j = i + 2; j < n; j++) {
            const c2 = s[j];
            if ((c1 === "(" || c1 === "*") && (c2 === ")" || c2 === "*")) {
                dp[i][j] = dp[i + 1][j - 1];
            }
            for (let k = i; k < j && !dp[i][j]; k++) {
                dp[i][j] = dp[i][k] && dp[k + 1][j];
            }
        }
    }
    return dp[0][n - 1];
};